<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>背包问题 - 动态规划经典算法</title>
    <link rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css">
    <link rel="stylesheet" href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
        }
        .hero-gradient {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
        }
        .card-hover {
            transition: all 0.3s ease;
        }
        .card-hover:hover {
            transform: translateY(-5px);
            box-shadow: 0 20px 40px rgba(0,0,0,0.1);
        }
        .code-block {
            background: #1e1e1e;
            color: #d4d4d4;
            border-radius: 12px;
            overflow: hidden;
        }
        .code-line {
            transition: background 0.2s ease;
        }
        .code-line:hover {
            background: rgba(255,255,255,0.05);
        }
        .drop-cap {
            float: left;
            font-size: 4rem;
            line-height: 1;
            font-weight: 700;
            margin-right: 0.5rem;
            color: #667eea;
        }
        .mermaid {
            display: flex;
            justify-content: center;
            margin: 2rem 0;
        }
        .tag {
            background: linear-gradient(135deg, #f093fb 0%, #f5576c 100%);
            color: white;
            padding: 0.25rem 1rem;
            border-radius: 9999px;
            font-size: 0.875rem;
            font-weight: 500;
            display: inline-block;
            margin-right: 0.5rem;
        }
    </style>
</head>
<body class="bg-gray-50">
    <!-- Hero Section -->
    <section class="hero-gradient text-white py-20 px-6">
        <div class="max-w-6xl mx-auto">
            <div class="text-center">
                <h1 class="text-5xl md:text-7xl font-bold mb-6 tracking-tight">背包问题</h1>
                <p class="text-xl md:text-2xl font-light mb-8 opacity-90">动态规划的经典之作</p>
                <div class="flex justify-center space-x-4 mb-12">
                    <span class="tag"><i class="fas fa-code mr-2"></i>动态规划</span>
                    <span class="tag"><i class="fas fa-cube mr-2"></i>01背包</span>
                    <span class="tag"><i class="fas fa-chart-line mr-2"></i>O(n·w)</span>
                </div>
            </div>
        </div>
    </section>

    <!-- Main Content -->
    <main class="max-w-6xl mx-auto px-6 py-16">
        <!-- Problem Description -->
        <section class="mb-16">
            <div class="bg-white rounded-2xl shadow-xl p-8 md:p-12 card-hover">
                <h2 class="text-3xl font-bold mb-6 text-gray-800 flex items-center">
                    <i class="fas fa-question-circle text-purple-600 mr-3"></i>
                    题目描述
                </h2>
                <div class="prose prose-lg max-w-none">
                    <p class="text-gray-700 leading-relaxed">
                        <span class="drop-cap">有</span>n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight[i]，价值是 value[i]。每件物品只能使用一次，求解将哪些物品装入背包可使价值总和最大。
                    </p>
                    <div class="bg-purple-50 border-l-4 border-purple-600 p-6 mt-6 rounded-r-lg">
                        <p class="font-semibold text-purple-900 mb-2">示例输入：</p>
                        <code class="text-purple-800">weight = [1, 3, 4], value = [15, 20, 30], w = 4</code>
                        <p class="font-semibold text-purple-900 mt-4 mb-2">示例输出：</p>
                        <code class="text-purple-800">35（选择第 1 和第 3 件物品）</code>
                    </div>
                </div>
            </div>
        </section>

        <!-- Visual Representation -->
        <section class="mb-16">
            <div class="bg-white rounded-2xl shadow-xl p-8 md:p-12 card-hover">
                <h2 class="text-3xl font-bold mb-6 text-gray-800 flex items-center">
                    <i class="fas fa-project-diagram text-purple-600 mr-3"></i>
                    算法可视化
                </h2>
                <div class="mermaid">
                    graph TD
                        A[背包问题] --> B[状态定义]
                        B --> C[dp数组: dp[i][j]]
                        C --> D[前i件物品]
                        C --> E[背包容量j]
                        C --> F[最大价值]
                        
                        A --> G[状态转移]
                        G --> H[不放入物品i]
                        H --> I[dp[i][j] = dp[i-1][j]]
                        G --> J[放入物品i]
                        J --> K[dp[i][j] = dp[i-1][j-weight[i]] + value[i]]
                        
                        A --> L[优化策略]
                        L --> M[二维数组 → 一维数组]
                        L --> N[倒序遍历防止重复]
                        
                        style A fill:#667eea,stroke:#fff,stroke-width:3px,color:#fff
                        style B fill:#764ba2,stroke:#fff,stroke-width:2px,color:#fff
                        style G fill:#764ba2,stroke:#fff,stroke-width:2px,color:#fff
                        style L fill:#764ba2,stroke:#fff,stroke-width:2px,color:#fff
                </div>
            </div>
        </section>

        <!-- Solution Approach -->
        <section class="mb-16">
            <div class="bg-white rounded-2xl shadow-xl p-8 md:p-12 card-hover">
                <h2 class="text-3xl font-bold mb-6 text-gray-800 flex items-center">
                    <i class="fas fa-lightbulb text-purple-600 mr-3"></i>
                    解题思路
                </h2>
                <div class="grid md:grid-cols-2 gap-6">
                    <div class="bg-gradient-to-br from-purple-50 to-pink-50 p-6 rounded-xl">
                        <h3 class="text-xl font-semibold mb-4 text-purple-900">
                            <i class="fas fa-layer-group mr-2"></i>状态定义
                        </h3>
                        <p class="text-gray-700">定义 dp[i][j] 表示从前 i 件物品中选择放入重量为 j 的背包中所获得的最大价值。</p>
                    </div>
                    <div class="bg-gradient-to-br from-blue-50 to-purple-50 p-6 rounded-xl">
                        <h3 class="text-xl font-semibold mb-4 text-blue-900">
                            <i class="fas fa-exchange-alt mr-2"></i>状态转移
                        </h3>
                        <ul class="space-y-2 text-gray-700">
                            <li><i class="fas fa-check-circle text-green-500 mr-2"></i>放入：dp[i][j] = dp[i-1][j-weight[i]] + value[i]</li>
                            <li><i class="fas fa-times-circle text-red-500 mr-2"></i>不放：dp[i][j] = dp[i-1][j]</li>
                        </ul>
                    </div>
                </div>
                <div class="mt-6 bg-gray-50 p-6 rounded-xl">
                    <p class="text-gray-700">
                        <i class="fas fa-clock text-purple-600 mr-2"></i>
                        <strong>时间复杂度：</strong>O(n·w)　　
                        <i class="fas fa-memory text-purple-600 mr-2"></i>
                        <strong>空间复杂度：</strong>O(n·w)，可优化至 O(w)
                    </p>
                </div>
            </div>
        </section>

        <!-- Code Implementation -->
        <section class="mb-16">
            <div class="bg-white rounded-2xl shadow-xl overflow-hidden card-hover">
                <div class="bg-gradient-to-r from-purple-600 to-pink-600 text-white p-6">
                    <h2 class="text-3xl font-bold flex items-center">
                        <i class="fas fa-code mr-3"></i>
                        示例代码（一维数组优化版）
                    </h2>
                </div>
                <div class="code-block p-6">
                    <pre class="text-sm md:text-base"><code><span class="text-purple-400">public int</span> <span class="text-yellow-300">knapsack</span>(<span class="text-purple-400">int[]</span> weight, <span class="text-purple-400">int[]</span> value, <span class="text-purple-400">int</span> w) {
    <span class="text-gray-500">// 获取物品数量</span>
    <span class="text-purple-400">int</span> n = weight.<span class="text-blue-300">length</span>;
    
    <span class="text-gray-500">// 创建一维动态规划数组，表示背包容量为j时的最大价值</span>
    <span class="text-purple-400">int[]</span> dp = <span class="text-purple-400">new int</span>[w + <span class="text-green-300">1</span>];

    <span class="text-gray-500">// 遍历每件物品</span>
    <span class="text-purple-400">for</span> (<span class="text-purple-400">int</span> i = <span class="text-green-300">0</span>; i < n; i++) {
        <span class="text-gray-500">// 从背包容量w开始，倒序遍历到当前物品的重量</span>
        <span class="text-gray-500">// 必须倒序遍历，防止物品被重复添加</span>
        <span class="text-purple-400">for</span> (<span class="text-purple-400">int</span> j = w; j >= weight[i]; j--) {
            <span class="text-gray-500">// 比较不放入当前物品和放入当前物品的价值大小</span>
            dp[j] = Math.<span class="text-blue-300">max</span>(dp[j], dp[j - weight[i]] + value[i]);
        }
    }

    <span class="text-gray-500">// 返回背包容量为w时的最大价值</span>
    <span class="text-purple-400">return</span> dp[w];
}</code></pre>
                </div>
            </div>
        </section>

        <!-- Key Points -->
        <section class="mb-16">
            <div class="bg-white rounded-2xl shadow-xl p-8 md:p-12 card-hover">
                <h2 class="text-3xl font-bold mb-6 text-gray-800 flex items-center">
                    <i class="fas fa-key text-purple-600 mr-3"></i>
                    关键要点
                </h2>
                <div class="grid md:grid-cols-3 gap-6">
                    <div class="text-center p-6 bg-gradient-to-br from-purple-100 to-pink-100 rounded-xl">
                        <i class="fas fa-sync-alt text-4xl text-purple-600 mb-4"></i>
                        <h3 class="text-xl font-semibold mb-2">倒序遍历</h3>
                        <p class="text-gray-700">一维数组优化时必须倒序，避免物品重复使用</p>
                    </div>
                    <div class="text-center p-6 bg-gradient-to-br from-blue-100 to-purple-100 rounded-xl">
                        <i class="fas fa-compress-alt text-4xl text-blue-600 mb-4"></i>
                        <h3 class="text-xl font-semibold mb-2">空间优化</h3>
                        <p class="text-gray-700">从二维数组优化到一维，空间复杂度降至O(w)</p>
                    </div>
                    <div class="text-center p-6 bg-gradient-to-br from-pink-100 to-purple-100 rounded-xl">
                        <i class="fas fa-balance-scale text-4xl text-pink-600 mb-4"></i>
                        <h3 class="text-xl font-semibold mb-2">决策过程</h3>
                        <p class="text-gray-700">每个物品都面临放入或不放入的选择</p>
                    </div>
                </div>
            </div>
        </section>
    </main>

    <script>
        mermaid.initialize({ 
            startOnLoad: true,
            theme: 'default',
            themeVariables: {
                primaryColor: '#667eea',
                primaryTextColor: '#fff',
                primaryBorderColor: '#764ba2',
                lineColor: '#5a67d8',
                secondaryColor: '#f7fafc',
                tertiaryColor: '#e9d8fd'
            }
        });
    </script>
</body>
</html>